package sort;

public class MergeSort {
    public void sort(int[] nums) {
        if (nums.length < 2) return;
        sort(nums, 0, nums.length - 1);
    }

    private void sort(int[] nums, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            sort(nums, left, mid); // 左排序
            sort(nums, mid + 1, right); // 右排序
            merge(nums, left, right);
        }
    }

    private void merge(int[] nums, int left, int right) {
        int mid = left + (right - left) / 2;
        int[] tmp = new int[nums.length];
        int k = left;
        int i = left;
        int j = mid + 1;
        while (i <= mid && j <= right) { // 常规情况，左右两边都有数据
            if (nums[i] < nums[j])
                tmp[k++] = nums[i++];
            else
                tmp[k++] = nums[j++];
        }
        while (i <= mid) // 只有左边有数据
            tmp[k++] = nums[i++];

        while (j <= right) // 只有右边有数据
            tmp[k++] = nums[j++];
        int t = left;
        while (t <= right) // 对原数组进行更新赋值
            nums[t] = tmp[t++];
    }

    public static void main(String[] args) {
        int[] nums = {1, 8, 6, 7, 9, 4, 5, 2, 3, 0};
        new MergeSort().sort(nums);
        Common.printArray(nums);
    }
}
